// https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/

// 算法思路总结：
// 1. 使用动态规划求解使字符串成为回文的最少插入次数
// 2. dp[i][j]表示使s[i..j]成为回文的最少插入次数
// 3. 当s[i]==s[j]时，次数等于中间子序列的次数
// 4. 当s[i]!=s[j]时，取左右子序列的最小值加1
// 5. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int minInsertions(string s) 
    {
        int m = s.size();
        vector<vector<int>> dp(m, vector<int>(m, INF));

        for (int i = m - 1 ; i >= 0 ; i--)
        {
            for (int j = i ; j < m; j++)
            {
                if (s[i] == s[j])
                {
                    if (i == j)
                        dp[i][j] = 0;
                    else if (i + 1 == j)
                        dp[i][j] = 0;
                    else 
                        dp[i][j] = dp[i + 1][j - 1];
                }
                else 
                {
                    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[0][m - 1];
    }
};

int main()
{
    string s1 = "mbadm", s2 = "leetcode";
    Solution sol;

    cout << sol.minInsertions(s1) << endl;
    cout << sol.minInsertions(s2) << endl;

    return 0;
}